import java.util.Arrays;

/**
 * @author gao
 * @date 2025/8/17 23:37
 */

public class MyBitSet {
    public byte[] elem;
    public int usedSize;

    public MyBitSet(byte[] elem) {
        this.elem = new byte[1];
    }

    /**
     * 有可能多给一个字节，但是无所谓
     * @param n 多少位
     */
    public MyBitSet(int n) {
        this.elem = new byte[n / 8 + 1];
    }

    /**
     * 设置某一位为1，证明数据出现过
     * @param val 查找的数据
     */
    public void set(int val) {
        if (val < 0) {
            throw new IndexOutOfBoundsException();
        }
        int arrayIndex = val / 8;
        // 扩容
        if (arrayIndex > elem.length - 1) {
            elem = Arrays.copyOf(elem, arrayIndex + 1);
        }
        int bitIndex = val % 8;
        elem[arrayIndex] |= (1 << bitIndex);
        usedSize++;
    }

    /**
     *
     * @param val 输入的数据
     * @return 判断当前位是不是1
     */
    public boolean get(int val) {
        if (val < 0) {
            throw new IndexOutOfBoundsException();
        }
        int arrayIndex = val / 8;
        int bitIndex = val % 8;
        if (arrayIndex >= elem.length) {
            return false;
        }

        return (elem[arrayIndex] & (1 << bitIndex)) != 0;
    }

    /**
     * 将对应位置置为0
     * @param val 输入的位数
     */
    public void reSet(int val) {
        if (val < 0) {
            throw new IndexOutOfBoundsException();
        }
        int arrayIndex = val / 8;
        int bitIndex = val % 8;
        elem[arrayIndex] &= ~(1 << bitIndex);
        usedSize--;
    }

    // 获取当前已经使用的位数
    public int getUsedSize() {
        return usedSize;
    }

    public static void main(String[] args) {
        int[] array = {1, 3, 7, 4, 12, 16, 19, 13, 22, 18};
        MyBitSet bitSet = new MyBitSet(22);
        for (int i = 0; i < array.length; i++) {
            bitSet.set(array[i]);
        }
        System.out.println(bitSet.get(7));
        System.out.println(bitSet.get(5));
        System.out.println(bitSet.get(50));
    }
}